home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / PowerLisp 2.01 / Supplemental Documentation / Documentation / Chapter 16. Hash Tables < prev    next >
Lisp/Scheme  |  1995-03-27  |  15KB  |  350 lines
  1. Common Lisp the Language, 2nd Edition
  2. -------------------------------------------------------------------------------
  3.  
  4. 16. Hash Tables
  5.  
  6. A hash table is a Lisp object that can efficiently map a given Lisp object to
  7. another Lisp object. Each hash table has a set of entries, each of which
  8. associates a particular key with a particular value. The basic functions that
  9. deal with hash tables can create entries, delete entries, and find the value
  10. that is associated with a given key. Finding the value is very fast, even if
  11. there are many entries, because hashing is used; this is an important advantage
  12. of hash tables over property lists.
  13.  
  14. A given hash table can associate only one value with a given key; if you try to
  15. add a second value, it will replace the first. Also, adding a value to a hash
  16. table is a destructive operation; the hash table is modified. By contrast,
  17. association lists can be augmented non-destructively.
  18.  
  19. Hash tables come in three kinds, the difference being whether the keys are
  20. compared with eq, eql, or equal. In other words, there are hash tables that
  21. hash on Lisp objects (using eq or eql) and there are hash tables that hash on
  22. tree structure (using equal).
  23.  
  24. Hash tables are created with the function make-hash-table, which takes various
  25. options, including which kind of hash table to make (the default being the eql
  26. kind). To look up a key and find the associated value, use gethash. New entries
  27. are added to hash tables using setf with gethash. To remove an entry, use
  28. remhash. Here is a simple example.
  29.  
  30. (setq a (make-hash-table))
  31. (setf (gethash 'color a) 'brown)
  32. (setf (gethash 'name a) 'fred)
  33. (gethash 'color a) => brown
  34. (gethash 'name a) => fred
  35. (gethash 'pointy a) => nil
  36.  
  37. In this example, the symbols color and name are being used as keys, and the
  38. symbols brown and fred are being used as the associated values. The hash table
  39. has two items in it, one of which associates from color to brown, and the other
  40. of which associates from name to fred.
  41.  
  42. Keys do not have to be symbols; they can be any Lisp object. Similarly, values
  43. can be any Lisp object.
  44.  
  45. [old_change_begin]
  46. When a hash table is first created, it has a size, which is the maximum number
  47. of entries it can hold. Usually the actual capacity of the table is somewhat
  48. less, since the hashing is not perfectly collision-free. With the maximum
  49. possible bad luck, the capacity could be very much less, but this rarely
  50. happens. If so many entries are added that the capacity is exceeded, the hash
  51. table will automatically grow, and the entries will be rehashed (new hash
  52. values will be recomputed, and everything will be rearranged so that the fast
  53. hash lookup still works). This is transparent to the caller; it all happens
  54. automatically.
  55. [old_change_end]
  56.  
  57. [change_begin]
  58. There is a discrepancy between the preceding description of the size of a hash
  59. table and the description of the :size argument in the specification below of
  60. make-hash-table.
  61.  
  62. X3J13 voted in June 1989 (HASH-TABLE-SIZE)   to regard the latter description
  63. as definitive: the :size argument is approximately the number of entries that
  64. can be inserted without having to enlarge the hash table. This definition is
  65. certainly more convenient for the user.
  66. [change_end]
  67.  
  68. -------------------------------------------------------------------------------
  69. Compatibility note: This hash table facility is compatible with Lisp Machine
  70. Lisp. It is similar to the hasharray facility of Interlisp, and some of the
  71. function names are the same. However, it is not compatible with Interlisp. The
  72. exact details and the order of arguments are designed to be consistent with the
  73. rest of MacLisp rather than with Interlisp. For instance, the order of
  74. arguments to maphash is different, there is no ``system hash table,'' and there
  75. is not the Interlisp restriction that keys and values may not be nil.
  76. -------------------------------------------------------------------------------
  77.  
  78. -------------------------------------------------------------------------------
  79.  
  80.    *  Hash Table Functions
  81.    *  Primitive Hash Function
  82.  
  83. -------------------------------------------------------------------------------
  84.  
  85. 16.1. Hash Table Functions
  86.  
  87. This section documents the functions for hash tables, which use objects as keys
  88. and associate other objects with them.
  89.  
  90. [Function]
  91. make-hash-table &key :test :size :rehash-size :rehash-threshold
  92.  
  93. This function creates and returns a new hash table. The :test argument
  94. determines how keys are compared; it must be one of the three values #'eq,
  95. #'eql, or #'equal, or one of the three symbols eq, eql, or equal. If no test is
  96. specified, eql is assumed.
  97.  
  98. [change_begin]
  99. X3J13 voted in January 1989 (HASH-TABLE-TESTS)   to add a fourth type of hash
  100. table: the value of #'equalp and the symbol equalp are to be additional valid
  101. possibilities for the :test argument.
  102.  
  103. Note that one consequence of the vote to change the rules of floating-point
  104. contagion (CONTAGION-ON-NUMERICAL-COMPARISONS)   (described in section 12.1) is
  105. to require =, and therefore also equalp, to compare the values of numbers
  106. exactly and not approximately, making equalp a true equivalence relation on
  107. numbers.
  108.  
  109. Another valuable use of equalp hash tables is case-insensitive comparison of
  110. keys that are strings.
  111. [change_end]
  112.  
  113. The :size argument sets the initial size of the hash table, in entries. (The
  114. actual size may be rounded up from the size you specify to the next ``good''
  115. size, for example to make it a prime number.) You won't necessarily be able to
  116. store precisely this many entries into the table before it overflows and
  117. becomes bigger, but this argument does serve as a hint to the implementation of
  118. approximately how many entries you intend to store.
  119.  
  120. [change_begin]
  121. X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED)   to clarify that the
  122. :size argument must be a non-negative integer.
  123.  
  124. X3J13 voted in June 1989 (HASH-TABLE-SIZE)   to regard the preceding
  125. description of the :size argument as definitive: it is approximately the number
  126. of entries that can be inserted without having to enlarge the hash table.
  127. [change_end]
  128.  
  129. The :rehash-size argument specifies how much to increase the size of the hash
  130. table when it becomes full. This can be an integer greater than zero, which is
  131. the number of entries to add, or it can be a floating-point number greater than
  132. 1, which is the ratio of the new size to the old size. The default value for
  133. this argument is implementation-dependent.
  134.  
  135. [old_change_begin]
  136. The :rehash-threshold argument specifies how full the hash table can get before
  137. it must grow. This can be an integer greater than zero and less than the
  138. :rehash-size (in which case it will be scaled whenever the table is grown), or
  139. it can be a floating-point number between zero and 1. The default value for
  140. this argument is implementation-dependent.
  141. [old_change_end]
  142.  
  143. [change_begin]
  144. X3J13 voted in June 1989 (HASH-TABLE-SIZE)   to replace the preceding
  145. specification of the :rehash-threshold argument with the following: The
  146. :rehash-threshold argument specifies how full the hash table can get before it
  147. must grow. It may be any real number between 0 and 1, inclusive. It indicates
  148. the maximum desired level of hash table occupancy. An implementation is
  149. permitted to ignore this argument. The default value for this argument is
  150. implementation-dependent.
  151. [change_end]
  152.  
  153. An example of the use of make-hash-table:
  154.  
  155. (make-hash-table :rehash-size 1.5
  156.                  :size (* number-of-widgets 43))
  157.  
  158. [Function]
  159. hash-table-p object
  160.  
  161. hash-table-p is true if its argument is a hash table, and otherwise is false.
  162.  
  163. (hash-table-p x) == (typep x 'hash-table)
  164.  
  165. [Function]
  166. gethash key hash-table &optional default
  167.  
  168. gethash finds the entry in hash-table whose key is key and returns the
  169. associated value. If there is no such entry, gethash returns default, which is
  170. nil if not specified.
  171.  
  172. gethash actually returns two values, the second being a predicate value that is
  173. true if an entry was found, and false if no entry was found.
  174.  
  175. setf may be used with gethash to make new entries in a hash table. If an entry
  176. with the specified key already exists, it is removed before the new entry is
  177. added. The default argument may be specified to gethash in this context; it is
  178. ignored by setf but may be useful in such macros as incf that are related to
  179. setf:
  180.  
  181. (incf (gethash a-key table 0))
  182.  
  183. means approximately the same as
  184.  
  185. (setf (gethash a-key table 0)
  186.       (+ (gethash a-key table 0) 1))
  187.  
  188. which in turn would be treated as simply
  189.  
  190. (setf (gethash a-key table)
  191.       (+ (gethash a-key table 0) 1))
  192.  
  193. [Function]
  194. remhash key hash-table
  195.  
  196. remhash removes any entry for key in hash-table. This is a predicate that is
  197. true if there was an entry or false if there was not.
  198.  
  199. [Function]
  200. maphash function hash-table
  201.  
  202. For each entry in hash-table, maphash calls function on two arguments: the key
  203. of the entry and the value of the entry; maphash then returns nil. If entries
  204. are added to or deleted from the hash table while a maphash is in progress, the
  205. results are unpredictable, with one exception: if the function calls remhash to
  206. remove the entry currently being processed by the function, or performs a setf
  207. of gethash on that entry to change the associated value, then those operations
  208. will have the intended effect. For example:
  209.  
  210. ;;; Alter every entry in MY-HASH-TABLE, replacing the value with
  211. ;;; its square root.  Entries with negative values are removed.
  212. (maphash #'(lambda (key val)
  213.              (if (minusp val)
  214.                  (remhash key my-hash-table)
  215.                  (setf (gethash key my-hash-table) (sqrt val))))
  216.          my-hash-table)
  217.  
  218. [change_begin]
  219. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  220. user side effects; see section 7.9.
  221. [change_end]
  222.  
  223. [Function]
  224. clrhash hash-table
  225.  
  226. This removes all the entries from hash-table and returns the hash table itself.
  227.  
  228. [Function]
  229. hash-table-count hash-table
  230.  
  231. This returns the number of entries in the hash-table. When a hash table is
  232. first created or has been cleared, the number of entries is zero.
  233.  
  234. [change_begin]
  235.  
  236. [Macro]
  237. with-hash-table-iterator (mname hash-table) {form}*
  238.  
  239. X3J13 voted in January 1989 (HASH-TABLE-PACKAGE-GENERATORS)   to add the macro
  240. with-hash-table-iterator.
  241.  
  242. The name mname is bound and defined as if by macrolet, with the body forms as
  243. its lexical scope, to be a ``generator macro'' such that successive invocations
  244. (mname) will return entries, one by one, from the hash table that is the value
  245. of the expression hash-table (which is evaluated exactly once).
  246.  
  247. At each invocation of the generator macro, there are two possibilities. If
  248. there is yet another unprocessed entry in the hash table, then three values are
  249. returned: t, the key of the hash table entry, and the associated value of the
  250. hash table entry. On the other hand, if there are no more unprocessed entries
  251. in the hash table, then one value is returned: nil.
  252.  
  253. The implicit interior state of the iteration over the hash table entries has
  254. dynamic extent. While the name mname has lexical scope, it is an error to
  255. invoke the generator macro once the with-hash-table-iterator form has been
  256. exited.
  257.  
  258. Invocations of with-hash-table-iterator and related macros may be nested, and
  259. the generator macro of an outer invocation may be called from within an inner
  260. invocation (assuming that its name is visible or otherwise made available).
  261.  
  262. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  263. user side effects; see section 7.9.
  264.  
  265. -------------------------------------------------------------------------------
  266. Rationale: This facility is a bit more flexible than maphash. It makes possible
  267. a portable and efficient implementation of loop clauses for iterating over hash
  268. tables (see chapter 26).
  269. -------------------------------------------------------------------------------
  270.  
  271. (setq turtles (make-hash-table :size 9 :test 'eq))
  272. (setf (gethash 'howard-kaylan turtles) '(musician lead-singer))
  273. (setf (gethash 'john-barbata turtles) '(musician drummer))
  274. (setf (gethash 'leonardo turtles) '(ninja leader blue))
  275. (setf (gethash 'donatello turtles) '(ninja machines purple))
  276. (setf (gethash 'al-nichol turtles) '(musician guitarist))
  277. (setf (gethash 'mark-volman turtles) '(musician great-hair))
  278. (setf (gethash 'raphael turtles) '(ninja cool rude red))
  279. (setf (gethash 'michaelangelo turtles) '(ninja party-dude orange))
  280. (setf (gethash 'jim-pons turtles) '(musician bassist))
  281.  
  282. (with-hash-table-iterator (get-turtle turtles)
  283.   (labels ((try (got-one &optional key value)
  284.              (when got-one      ;Remember, keys may show up in any order
  285.                (when (eq (first value) 'ninja)
  286.                  (format t "~%~:(~A~): ~{~A~^, ~}"
  287.                          key (rest value)))
  288.                (multiple-value-call #'try (get-turtle)))))
  289.     (multiple-value-call #'try (get-turtle))))     ;Prints 4 lines
  290. Michaelangelo: PARTY-DUDE, ORANGE
  291. Leonardo: LEADER, BLUE
  292. Raphael: COOL, RUDE, RED
  293. Donatello: MACHINES, PURPLE
  294.   => nil
  295.  
  296. [change_end]
  297.  
  298. [change_begin]
  299.  
  300. [Function]
  301. hash-table-rehash-size hash-table
  302. hash-table-rehash-threshold hash-table
  303. hash-table-size hash-table
  304. hash-table-test hash-table
  305.  
  306. X3J13 voted in March 1989 (HASH-TABLE-ACCESS)   to add four accessor functions
  307. that return values suitable for use in a call to make-hash-table in order to
  308. produce a new hash table with state corresponding to the current state of the
  309. argument hash table.
  310.  
  311. hash-table-rehash-size returns the current rehash size of a hash table.
  312.  
  313. hash-table-rehash-threshold returns the current rehash threshold.
  314.  
  315. hash-table-size returns the current size of a hash table.
  316.  
  317. hash-table-test returns the test used for comparing keys. If the test is one of
  318. the standard test functions, then the result will always be a symbol, even if
  319. the function itself was specified when the hash-table was created. For example:
  320.  
  321. (hash-table-test (make-hash-table :test #'equal)) => equal
  322.  
  323. Implementations that extend make-hash-table by providing additional
  324. possibilities for the :test argument may determine how the value returned by
  325. hash-table-test is related to such additional tests.
  326. [change_end]
  327.  
  328. -------------------------------------------------------------------------------
  329.  
  330. 16.2. Primitive Hash Function
  331.  
  332. The function sxhash is a convenient tool for the user who needs to create more
  333. complicated hashed data structures than are provided by hash-table objects.
  334.  
  335. [Function]
  336. sxhash object
  337.  
  338. sxhash computes a hash code for an object and returns the hash code as a
  339. non-negative fixnum. A property of sxhash is that (equal x y) implies (=
  340. (sxhash x) (sxhash y)).
  341.  
  342. The manner in which the hash code is computed is implementation-dependent but
  343. independent of the particular ``incarnation'' or ``core image.'' Hash values
  344. produced by sxhash may be written out to files, for example, and meaningfully
  345. read in again into an instance of the same implementation.
  346.  
  347. -------------------------------------------------------------------------------
  348.  
  349.  
  350.